package com.cat.dynamicPlanning02;

import java.util.stream.IntStream;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/matchsticks-to-square/
 * @create 2025/11/5 18:35
 * @since JDK17
 */

public class Solution43 {
    int[] dp;
    boolean dfs(int[] arr, int status, int target, int rest, int cnt) {
        if (cnt == 4) {
            return status == 0;
        }
        if (dp[status] != 0) {
            return dp[status] == 1;
        }
        boolean ans = false;
        for (int i = 0; i < arr.length; i++) {
            if (ans) {
                break;
            }
            if ((status >> i & 1) != 0) {
                if (rest > arr[i]) {
                    ans = dfs(arr, status ^ (1 << i), target, rest - arr[i], cnt);
                } else if (rest == arr[i]){
                    ans = dfs(arr, status ^ (1 << i), target, target, cnt + 1);
                }
            }
        }
        dp[status] = ans ? 1 : -1;
        return ans;
    }

    public boolean makesquare(int[] matchsticks) {
        int n = matchsticks.length, sum = IntStream.of(matchsticks).sum(), target = sum / 4;
        if (sum % 4 != 0) {
            return false;
        }
        dp = new int[1 << n];
        return dfs(matchsticks, (1 << n) - 1, target, target, 0);
    }
}
